We propose a multi-dimensional (M-D) sparse Fourier transform inspired by theidea of the Fourier projection-slice theorem, called FPS-SFT. FPS-SFT extractssamples along lines (1-dimensional slices from an M-D data cube), which areparameterized by random slopes and offsets. The discrete Fourier transform(DFT) along those lines represents projections of M-D DFT of the M-D data ontothose lines. The M-D sinusoids that are contained in the signal can bereconstructed from the DFT along lines with a low sample and computationalcomplexity provided that the signal is sparse in the frequency domain and thelines are appropriately designed. The performance of FPS-SFT is demonstratedboth theoretically and numerically. A sparse image reconstruction applicationis illustrated, which shows the capability of the FPS-SFT in solving practicalproblems.
展开▼